In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.
Formally, an (r,g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an (r,g)-graph exists for any combination of r ≥ 2 and g ≥ 3. An (r,g)-cage is an (r,g)-graph with the fewest possible number of vertices, among all (r,g)-graphs.
If a Moore graph exists with degree r and girth g, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth g must have at least
vertices, and any cage with even girth g must have at least
vertices. Any (r,g)-graph with exactly this many vertices is by definition a Moore graph and therefore automatically a cage.
There may exist multiple cages for a given combination of r and g. For instance there are three nonisomorphic (3,10)-cages, each with 70 vertices : the Balaban 10-cage, the Harries graph and the Harries-Wong graph. But there is only one (3,11)-cage : the Balaban 11-cage (with 112 vertices).
A degree-one graph has no cycle, and a connected degree-two graph has girth equal to its number of vertices, so cages are only of interest for r ≥ 3. The (r,3)-cage is a complete graph Kr+1 on r+1 vertices, and the (r,4)-cage is a complete bipartite graph Kr,r on 2r vertices.
Other notable cages include the Moore graphs:
The numbers of vertices in the known (r,g) cages, for values of r > 2 and g > 2 are:
g: | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
r = 3: | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
---|---|---|---|---|---|---|---|---|---|---|
r = 4: | 5 | 8 | 19 | 26 | 67 | 80 | 728 | |||
r = 5: | 6 | 10 | 30 | 42 | 170 | 2730 | ||||
r = 6: | 7 | 12 | 40 | 62 | 312 | 7812 | ||||
r = 7: | 8 | 14 | 50 | 90 |